package main

import (
	"fmt"
	"math"
	"slices"
)

func productExceptSelf(nums []int) []int {
	n := len(nums)
	left, right := make([]int, n, n), make([]int, n, n)
	left[0], right[n-1] = nums[0], nums[n-1]
	for i := 1; i < n; i++ {
		left[i] = nums[i] * left[i-1]
		right[n-i-1] = nums[n-i-1] * right[n-i]
	}
	ans := make([]int, n, n)
	for i := 0; i < n; i++ {
		if i == 0 {
			ans[i] = right[i+1]
		} else if i == n-1 {
			ans[i] = left[i-1]
		} else {
			ans[i] = left[i-1] * right[i+1]
		}

	}

	return ans
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func BuildList(arr []int) *ListNode {
	head := &ListNode{}
	slices.Reverse(arr)
	for _, v := range arr {
		temp := &ListNode{Val: v}
		temp.Next = head.Next
		head.Next = temp
	}
	return head.Next
}
func isPalindrome(head *ListNode) bool {
	n := 0
	pre := head
	t := head
	for t != nil {
		t = t.Next
		n++
	}
	node := &ListNode{}
	node.Next = head
	for n > 1 {
		node = node.Next
		n = n - 2
	}
	var post *ListNode
	if n == 1 {
		post = node.Next.Next
	} else {
		post = node
	}
	node.Next = nil

	postRe := reverse(post)

	printList(postRe)
	printList(pre)

	for pre != nil && postRe != nil {
		if pre.Val != postRe.Val {
			return false
		}
		pre = pre.Next
		postRe = postRe.Next
	}
	return true
}
func printList(head *ListNode) {
	fmt.Printf("List = ")
	for head != nil {
		fmt.Printf("%v ", head.Val)
		head = head.Next
	}
	fmt.Println()
}
func reverse(post *ListNode) *ListNode {
	node := &ListNode{}
	for post != nil {
		temp := post
		post = post.Next
		temp.Next = node.Next
		node.Next = temp
	}
	return node.Next
}
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	ans := &ListNode{}
	p := ans
	for list1 != nil || list2 != nil {
		if list1 != nil && list2 != nil {
			if list1.Val < list2.Val {
				p.Next = list1
				list1 = list1.Next
			} else {
				p.Next = list2
				list2 = list2.Next
			}
		} else if list1 != nil {
			p.Next = list1
			list1 = list1.Next
		} else {
			p.Next = list2
			list2 = list2.Next
		}
		p = p.Next
		p.Next = nil
	}

	return ans.Next
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	pre := &ListNode{Val: -1, Next: head}
	ans := pre
	ptr := pre
	length := 0
	for ptr != nil {
		ptr = ptr.Next
		length++
	}
	for length > n+1 {
		pre = pre.Next
		length--
	}
	pre.Next = pre.Next.Next

	return ans.Next
}
func swapPairs(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	if head.Next == nil {
		return head
	}

	node := &ListNode{Val: -1, Next: nil}
	ptr := node
	for head != nil {
		first, second := swapTwo(head)
		if second != nil {
			head = second.Next
		} else {
			head = nil
		}

		ptr.Next = first
		ptr = second
	}
	return node.Next
}
func swapTwo(head *ListNode) (*ListNode, *ListNode) {
	if head == nil {
		return nil, nil
	}
	if head.Next == nil {
		return head, nil
	}
	next := head.Next
	head.Next = next.Next
	next.Next = head
	return next, head
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	node := &ListNode{Val: -1, Next: head}
	ptr := node
	for head != nil {
		pre, next := reverseK(head, k)
		ptr.Next = pre
		if next != nil {
			head = next.Next
		} else {
			head = next
		}
		ptr = next
	}
	return node.Next
}
func reverseK(head *ListNode, k int) (*ListNode, *ListNode) {
	if head == nil {
		return nil, nil
	}
	ptr := head
	t := k
	for ptr != nil && t != 0 {
		ptr = ptr.Next
		t--
	}
	if t != 0 {
		return head, nil
	}

	pre := &ListNode{Val: -1, Next: head}
	next := pre
	for k > 0 {
		temp := head
		head = head.Next

		temp.Next = pre.Next
		pre.Next = temp
		next = next.Next
		k--
	}
	next.Next = head
	return pre.Next, next
}
func sortList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	first, second := split1(head)
	if first == nil || second == nil {
		return merge(first, second)
	}

	return merge(sortList(first), sortList(second))

}

func split1(head *ListNode) (*ListNode, *ListNode) {
	if head == nil {
		return nil, nil
	}
	if head.Next == nil {
		return head, nil
	}
	slow, fast := &ListNode{Next: head}, head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}
	tail := slow.Next
	slow.Next = nil

	return head, tail
}

func merge(l1, l2 *ListNode) *ListNode {
	node := &ListNode{}
	ptr := node
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			ptr.Next = l1
			l1 = l1.Next
		} else {
			ptr.Next = l2
			l2 = l2.Next
		}
		ptr = ptr.Next
	}
	if l1 == nil {
		l1 = l2
	}
	for l1 != nil {
		ptr.Next = l1
		l1 = l1.Next

		ptr = ptr.Next
	}
	return node.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
	minSearchNode := func() *ListNode {
		min := &ListNode{Val: math.MaxInt32}
		index := -1
		for i, list := range lists {
			if list == nil {
				continue
			}
			if list.Val < min.Val {
				min = list
				index = i
			}
		}
		if index == -1 {
			return nil
		}
		lists[index] = min.Next
		return min
	}
	ans := &ListNode{}
	ptr := ans
	minNode := ans
	for minNode != nil {
		minNode = minSearchNode()

		ptr = ptr.Next
	}
	return ans.Next
}

type LRUCache struct {
	capacity int
	mp       map[int]*HNode
	head     *HNode
	tail     *HNode
	size     int
}
type HNode struct {
	Val  int
	Key  int
	Pre  *HNode
	Next *HNode
}

func Constructor(capacity int) LRUCache {
	head := &HNode{}
	tail := &HNode{}
	head.Next = tail
	tail.Pre = head

	return LRUCache{
		capacity: capacity,
		mp:       map[int]*HNode{},
		head:     head,
		tail:     tail,
		size:     0,
	}
}

func (this *LRUCache) Get(key int) int {
	if value, ok := this.mp[key]; ok {
		this.moveToHead(value)
		return value.Val
	} else {
		return -1
	}
}
func (this *LRUCache) moveToHead(value *HNode) {
	this.remove(value)
	this.addHead(value)
}
func (this *LRUCache) remove(value *HNode) {
	value.Pre.Next = value.Next
	value.Next.Pre = value.Pre
}
func (this *LRUCache) addHead(value *HNode) {
	value.Next = this.head.Next
	value.Pre = this.head

	this.head.Next.Pre = value
	this.head.Next = value
}
func (this *LRUCache) Put(key int, value int) {
	if this.capacity <= 0 {
		return
	}

	if v, ok := this.mp[key]; ok {
		v.Val = value
		this.moveToHead(v)
		return
	}

	this.size++
	if this.size > this.capacity {
		this.size--
		last := this.tail.Pre
		this.remove(last)
		delete(this.mp, last.Key)
	}
	node := &HNode{Key: key, Val: value}
	this.addHead(node)
	this.mp[key] = node
}
func exist(board [][]byte, word string) bool {
	set := map[int]bool{}
	var dfs func(i, j, index int) bool
	m, n := len(board), len(board[0])
	l := len(word)
	check := func(i, j int) bool {
		return 0 <= i && i < m && 0 <= j && j < n
	}
	result := []string{}
	dfs = func(i, j, index int) bool {
   		if index == l {
			return true
		}

		target := i*m + j
		if set[target] || !check(i, j) || word[index] != board[i][j] {
			return false
		}
		set[target] = true
		ch := string(board[i][j])
		result = append(result, ch)
		ans := dfs(i-1, j, index+1) || 
			dfs(i+1, j, index+1) || 
			dfs(i, j-1, index+1) || 
			dfs(i, j+1, index+1)

		set[target] = false
		result = result[:len(result)-1]
		return ans
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if dfs(i, j, 0) {
				return true
			}
		}
	}
	return false
}
func testExist() {
	board := [][]byte{
		{'A', 'B', 'C', 'E'},
		{'S', 'F', 'E', 'S'},
		{'A', 'D', 'E', 'E'},
	}
	exist(board, "ABCESEEEFS")
}
func main() {
	// fmt.Println(productExceptSelf([]int{1, 2, 3, 4}))
	// isPalindrome(BuildList([]int{1, 2, 3, 4, 5, 4, 3, 2, 1}))
	// printList(mergeTwoLists(BuildList([]int{1, 2, 3, 4}), BuildList([]int{1, 2, 3, 4})))
	// removeNthFromEnd(BuildList([]int{1, 2, 3, 4, 5}), 2)
	// swapPairs(BuildList([]int{1, 2, 3, 4, 5, 6}))
	// printList(reverseKGroup(BuildList([]int{1,2,3,4,5,6,7,8}), 2))
	// printList(sortList(BuildList([]int{3})))
	// printList(mergeKLists([]*ListNode{
	// 	BuildList([]int{1, 4, 5}),
	// 	BuildList([]int{1, 3, 4}),
	// 	BuildList([]int{4, 5}),
	// }))
	// testLRUCache()
	// testQueue()
	testExist()
}
